package com.jacky.dp;

public class 最长公共子序列_1143 {

    /**
     * https://leetcode.cn/problems/longest-common-subsequence/solution/zui-chang-gong-gong-zi-xu-lie-tu-jie-dpz-6mvz/
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int length1 = text1.length(), length2 = text2.length();
        //定义一个dp数组,存储text1和text2字符串，每个字符最长公共子序列
        int[][] f = new int[length1 + 1][length2 + 1];
        //遍历text1和text2时候，从1开始的话，f[i - 1][j - 1]就不会下标越界
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                //如果两个字符串的最后一位相等，那么问题就转化成了字符串text1的[1,j-1]区间和字符串text2的[1,j-1]区间的最长公共子序列长度再加上一，即f[i][j] = f[i - 1][j - 1] + 1
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    //如果两个字符串的最后一位不相等，当前元素最长公共子串为，f[i - 1][j]和f[i][j - 1]较大的值
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[length1][length2];
    }
}
